#include <iostream>
#include <string>
#include <stack>
#include <algorithm>
using namespace std;

// LeetCode 32. 最长有效括号
// https://leetcode.cn/problems/longest-valid-parentheses/description/?envType=study-plan-v2&envId=leetcode-75
// 给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
//
// 示例 1：
// 输入：s = "(()"
// 输出：2
// 解释：最长有效括号子串是 "()"




class Solution {
    public:
        int longestValidParentheses(string s) {
            stack<int> st;
            st.push(-1);
    
            int max_length=0;
            for(int i=0;i<s.length();i++)
            {
                if(s[i]=='(') 
                {
                    st.push(i);
                }
                if(s[i]==')')
                {
                    st.pop();
                    if(st.empty())
                    {
                        st.push(i);
                    }
                    else{
                        max_length=max(max_length,i-st.top());
                    }
                }
            }
            return max_length;
        }
    };